1. Field of the Invention
This invention relates to computer system design and particularly to multi-node request fairness algorithms.
2. Description of Background
Historically, contention management schemes have been introduced in multi-node system to ensure timely processing of requests, to avoid system deadlocks, and/or to ensure system serialization, as applicable.
Of these management schemes the simplest is the basic protocol reject algorithm, where requests are sent from one node to the next and in the case of contention, the request on the remote node is rejected back to the requesting node, for an eventual retry under the presumption that by the time the request enters the remote node for a second time, the point of contention has been resolved and ownership of the line/data can be given to the remote requesting processor. In the cases where contention persists, continual rejecting and re-launching of the request persists until the contention is resolved and the requesting processor obtains ownership.
At the next level of complexity, hang detect algorithm have been introduced to designs to allow operations that have persisted in multi-node systems for an excessive period of time to stall new requests in an attempt to resolve the point of conflict before a noticeable stall can occur and operation timeout can be encountered.
In the more complex case where full ordering is required, system serialization algorithms are typically introduced that queue events in the order that they typically received at a central facility in the system. This ensures the ordering of events at the cost of increased hardware complexity.
In either of these cases, the management of the contention handling is typically done after a lengthy delay is detected in the system and an after-the-fact algorithm has to come into play, or a strict ordering algorithm is observed which is unrealistic for all types of operations as it is neither requisite nor affordable from a hardware investment and processing timeliness perspective.
If we step back and re-examine the basic protocol reject algorithm, ordering is observed assuming that the contention over a single point in the system is infrequent and the eventuality of the request obtaining ownership of the line will occur within a timely enough manner that any improved algorithm and the investment it requires is unnecessary.
Unfortunately, all of these algorithms fail to address the underlying issue within the system that produces the source of contention. This is the simple fact that under these algorithms previously described, new requests are not prevented from entering the system until either all interface hardware is consumed or the system has reached a point where all new requests must be stopped to prevent either a deadlock or a major system timeout or clockstop.
As a result, all of these algorithms typically address the contention after the fact and dismiss timeliness for design simplicity, with the exception of serialization logic which trades off accuracy for complexity.
The invention described herein seeks to maintain simplicity, while addressing contention and the timeliness that improved algorithms bring.